package binaryTree;


import javax.jnlp.ClipboardService;
import java.util.*;

public class Class652 {

    HashMap<String, Integer> hashMap;
    LinkedList<TreeNode> linkedList;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        if (root == null) {
            return null;
        }
        hashMap = new HashMap<>();
        linkedList = new LinkedList<>();
        traverse(root);
        return linkedList;
    }

    public String traverse(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String left = traverse(root.left);
        String right = traverse(root.right);
        String subTree = left + right + root.val;
        Integer freq = hashMap.getOrDefault(subTree, 0);
        //只有freq==1才说明有重复的子树木　　这时候才加ｌｉｓｔ集合里面　之后有重复的就不加入了直接在ｍａｐ对应ｋｅｙ值的数目加１
        if (freq == 1) {
            linkedList.add(root);
        }
        hashMap.put(subTree, freq + 1);
        return subTree;
    }

    //输出一个二叉树所有子树的后序遍历
    LinkedList<String> list=new LinkedList<>();
    public List<String>  findSubTree(TreeNode root){
        traverse1(root);
        return  list;
    }
    public   String traverse1(TreeNode root){
        if (root==null){
            return "";
        }
        String left = traverse1(root.left);
        String right = traverse1(root.right);
        //todo:这句话很关键　　老是会想不明白
        String res=left+right+root.val;
        list.add(res);
        return res;
    }





    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(2);
        TreeNode treeNode4 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(4);
        TreeNode treeNode6 = new TreeNode(4);
        TreeNode treeNode7 = new TreeNode(4);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode4;
//        treeNode2.left = treeNode5;
//        treeNode4.left = treeNode3;
//        treeNode4.right = treeNode6;
//        treeNode3.left = treeNode7;
        Class652 class652 = new Class652();
//        class652.dfs(treeNode1);
      class652.findDuplicateSubtrees(treeNode1);
//        System.out.println(class652.traverse(treeNode1));
//        for (TreeNode root :
//                class652.linkedList) {
//            System.out.println(root.val);
//        }

//        Iterator<Map.Entry<String, Integer>> iterator = class652.hashMap.entrySet().iterator();
//        while (iterator.hasNext()) {
//            Map.Entry<String, Integer> entry = iterator.next();
//            System.out.println(entry.getKey());
//            System.out.println(entry.getValue());
//
//        }

        List<String> subTree = class652.findSubTree(treeNode1);
        for (String a:
             subTree) {
            System.out.println(a);
        }


    }
}
